ОБОБЩЕННЫЕ НЕДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 

Баумгертнер Светлана Викторовна, кандидат физико-математических наук, старший преподаватель, кафедра прикладной математики и информатики, Тольяттинский государственный
университет (г. Тольятти, ул. Белорусская, 14), S-Baumgertner@yandex.ru
Мельников Борис Феликсович, доктор физико-математических наук, профессор, кафедра прикладной математики и информатики, Тольяттинский государственный университет (г. Тольятти,
ул. Белорусская, 14), B.Melnikov@tltsu.ru 

519.178 

Рассматривается формализм, предназначенный для представления специального расширения класса конечных автоматов – так называемых обобщенных недетерминированных конечных автоматов. Из изложенных в статье алгоритмов эквивалентного преобразования определяемых нами автоматов и аналога теоремы Клини для них вытекает не столько эквивалентность их и обычных конечных автоматов (эта эквивалентность очевидна априори), сколько возможность определения операции дополнения (и вообще обобщенных регулярных выражений) обычными «автоматными» методами.
Также в статье описан метод построения конкретного обобщенного автомата, который определяет заданное обобщенное регулярное выражение. Данный метод вытекает из доказательства аналога теоремы Клини. Представленные расширенные возможности для описания регулярных языков могут быть полезны в некоторых приложениях, например, в контекстном поиске. 

недетерминированные конечные автоматы, обобщенные регулярные выражения, алгоритмы эквивалентного преобразования, аналог теоремы Клини. 

1. Баумгертнер, С. Мультиэвристический подход к проблеме звездно-высотной минимизации недетерминированных конечных автоматов / С. Баумгертнер, Б. Мельников // Вестник Воронежского государственного университета. Серия: Cистемный анализ и информационные технологии. – 2010. – № 1. – C. 5–7.
2. Баумгертнер, С. Математическая модель автоматов для обобщенных регулярных выражений / С. Баумгертнер, Б. Мельников // Эвристические алгоритмы и распределенные вычисления в прикладных задачах : кол. моногр. – Тольятти : Изд-во ТГУ, 2012. – С. 16–23.
3. Баумгертнер, С. Аналог теоремы Клини для обобщенных недетерминированных конечных автоматов / С. Баумгертнер // Вектор науки Тольяттинского государственного университета. – 2012. – № 4 (22). – С. 23–25.
4. Саломаа, А. Жемчужины теории формальных языков / А. Саломаа. – М. : Мир, 1986. – 159 с.
5. Melnikov, B. Extended nondeterministic finite automata / B. Melnikov // Fundamenta Informaticae. – 2010. – Vol. 104, Т. 3. – Р. 255–265.
6. Melnikov, B. Some more on the finite automata / B. Melnikov, A. Vakhitova // J. of Applied Math. and Comp. (The Korean J. of Comp. Appl. Math.). – 1998. – Vol. 5, № 3. – Р. 495–506.
7. Melnikov, B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems / B. Melnikov // Fundamenta Informaticae. – 2010. – Vol. 104, № 3. – Р. 267–283.